import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        // int[] retArr = test.twoSum(new int[]{3, 9, 12, 15}, 18);
        // for(int i = 0; i < retArr.length; i++) {
        //     System.out.print(retArr[i] + " ");
        // }

        int[] nums = new int[]{1,0,-1,0,-2,2};
        List<List<Integer>> result = test.fourSum(nums, 0);
        for(int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i).toString());
        }
    }

    public int[] twoSum1(int[] price, int target) {
        /**
         * 两数之和
         * 解法：使用暴力解法
         * 超出时间限制
         * */
        // 1 预处理
        int n = price.length;

        // 2 暴力枚举
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                if(price[i] + price[j] == target) {
                    return new int[] {price[i], price[j]};
                }
            }
        }
        return new int[]{};
    }

    public int[] twoSum(int[] price, int target) {
        /**
         * 两数之和
         * 解法：利用单调性双指针
         * 超出时间限制
         * */
        // 1 预处理
        int n = price.length;

        // 2 双指针查找
        int left = 0;
        int right = n-1;
        while(left < right) {
            if(price[left] + price[right] == target) {
                return new int[]{price[left], price[right]};
            } else if(price[left] + price[right] > target) {
                // -最小+最大 > 目标，那么任意+最大也一定会大于目标，故舍去
                right --;
            } else {
                // -最小+最大 < 目标，那么任意+最小也一定小于目标，故舍去
                left ++;
            }
        }
        return new int[]{};
    }

    public List<List<Integer>> threeSum(int[] nums) {
        /**
         * 三数之和
         * 找出所有和为0的组合
         * 解法：双指针算法（不尝试暴力解法是因为，O(n³)必定超时）
         * */
        // 1 预处理
        Arrays.sort(nums);
        int n = nums.length;

        // 2 双指针逻辑
        // - 定义返回数组
        List<List<Integer>> retArray = new ArrayList<>();
        for(int i = n-1; i >= 2; i--) {
            int target = -nums[i];
            int left = 0;
            int right = i-1;
            while(left < right) {
                if(nums[left] + nums[right] == target) {
                    // 符合条件，还需去重，只要我们每次按照升序进行存放，即有序
                    List<Integer> tempArray = new ArrayList<>();
                    tempArray.add(nums[left]);
                    tempArray.add(nums[right]);
                    tempArray.add(nums[i]);
                    // 判重
                    if(!retArray.contains(tempArray)) {
                        retArray.add(tempArray);
                    }
                    // 步进
                    left ++;
                    right --;
                } else if(nums[left] + nums[right] > target) {
                    // 最小+最大 > 目标，那么任意+最大也一定会大于目标，故舍去最大
                    right --;
                } else if(nums[left] + nums[right] < target){
                    // 最小+最大 < 目标，那么任意+最小也一定会小于目标，故舍去最小
                    left ++;
                }
            }
        }
        return retArray;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        /**
         * 四数之和
         * 简单轻松，掌握方法，明天总结
         * */
        // 1 预处理
        int n = nums.length;
        Arrays.sort(nums);

        // 2 双指针，固2找2
        List<List<Integer>> retArray = new ArrayList<>();
        for(int i = 0; i < n-3; i++) {
            for(int j = i+1; j < n-2; j++) {
                //-记录目标值（值可能溢出，需要使用long）
                long tempTarget = (long)target - nums[i] - nums[j];
                int left = j+1;
                int right = n-1;
                while(left < right) {
                    if(nums[left] + nums[right] == tempTarget) {
                        // -符合条件，先记录（升序）
                        List<Integer> tempArray = new ArrayList<>();
                        tempArray.add(nums[i]);
                        tempArray.add(nums[j]);
                        tempArray.add(nums[left]);
                        tempArray.add(nums[right]);
                        // -判重
                        if(!retArray.contains(tempArray)) {
                            retArray.add(tempArray);
                        }
                        // -步进
                        left ++;
                        right --;
                    } else if(nums[left] + nums[right] < tempTarget) {
                        left ++;
                    } else if(nums[left] + nums[right] > tempTarget) {
                        right --;
                    }
                }
            }
        }
        return retArray;
    }
}
